#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/10/27 8:47
# ===========================================
#       题目名称： 64. 最小路径和
#       题目地址： https://leetcode.cn/problems/minimum-path-sum/
#       题目描述： https://note.youdao.com/s/VjIUrvCD
# ===========================================
from typing import *


class Solution:
    """
        通过动态规划实现
        1   3   1       1   4   5           取最小的 没有就直接算
        1   5   1       2   7   6
        4   2   1       6   8   7
    """

    def minPathSum(self, grid: List[List[int]]) -> int:
        # 获取size
        m, n = len(grid), len(grid[0])
        # 定义棋盘
        dp = [[1] * n for _ in range(m)]
        for x in range(m):
            for y in range(n):
                if x - 1 > -1 and y - 1 > -1:
                    min_val = min(dp[x - 1][y], dp[x][y - 1])
                    dp[x][y] = grid[x][y] + min_val
                else:
                    if x - 1 > -1:
                        dp[x][y] = grid[x][y] + dp[x - 1][y]
                        continue
                    if y - 1 > -1:
                        dp[x][y] = grid[x][y] + dp[x][y - 1]
                        continue
                    dp[x][y] = grid[x][y]
        return dp[m - 1][n - 1]


if __name__ == '__main__':
    s = Solution()
    # 7
    print("grid = [[1,3,1],[1,5,1],[4,2,1]] =>", s.minPathSum(grid=[[1, 3, 1], [1, 5, 1], [4, 2, 1]]))
    # 12
    print("grid = [[1,2,3],[4,5,6]] =>", s.minPathSum(grid=[[1, 2, 3], [4, 5, 6]]))
    # 0
    print("grid = [[0]] =>", s.minPathSum(grid=[[0]]))
